package cn.tansanqinger.linked;

import org.w3c.dom.Node;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;

interface IDoublyLink<T>{
    void add(T data);//添加数据
    int size();//返回链表长度
    T[] toArrayJust();//返回所有数据，正向
    T[] toArrayAgainst();//逆向输出所有数据
    T get(int index);//返回要查询的数据
    T remove(int index);//删除数据
    T set(int index, T data);//修改数据
}
class DoublyLinkImpl<T> implements IDoublyLink<T>{
    private Node root;//根结点
    private Node end; //尾结点
    private int size; //记录长度
    @Override
    public void add(T data) {
        Node node = new Node(data);//实例化结点
        if(this.root==null){//判断根结点是否为空
            this.root = node;
            this.end = node;
        } else {
            node.last = this.end;//该实例化结点保存的上结点保存上一个结点
            this.end.next = node;//保存下一个结点
            this.end = node;//移动指针
        }
        this.size ++;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public T[] toArrayJust() {
        if(this.size==0){
            return null;
        } else {
            return array(this.root,true);
        }
    }

    @Override
    public T[] toArrayAgainst() {
        if(this.size==0){
            return null;
        } else {
            return array(this.end,false);
        }
    }

    @Override
    public T get(int index) {
        if(this.size==0 || this.size<=index || index<0){//排除干扰
            return null;
        } else {
            Node list;
            //判断从哪端开始查询
            if(this.size/2>index){
                list = this.root;
                return (T) put(list,index,true).data;
            } else {
                list = this.end;
                return (T) put(list,index,false).data;
            }
        }
    }

    @Override
    public T remove(int index) {
        Object dataNode;
        if(this.size==0 || this.size<=index || index<0){//排除干扰
            return null;
        } else if(index == 0){
            dataNode = this.root.data;
            this.root = this.root.next;
            this.root.last = null;
        } else if(index == this.size-1){
            dataNode = this.end.data;
            this.end = this.end.last;
            this.end.next = null;
        }else {

            Node list;
            //判断从哪端开始查询
            if(this.size/2>index-1){
                list = put(this.root,index-1,true);
                dataNode = list.next.data;
                list.next = list.next.next;
                list.next.last = list;
            } else {
                list = put(this.end,index+1,false);
                dataNode = list.last.data;
                list.last = list.last.last;
                list.last.next = list;
            }
        }
        this.size--;
        return (T) dataNode;
    }

    @Override
    public T set(int index, T data) {
        if(this.size==0 || this.size<=index || index<0){//排除干扰
            return null;
        } else {
            Node list;
            //判断从哪端开始查询
            if(this.size/2>index){
                list = put(this.root,index,true);
            } else {
                list = put(this.end,index,false);
            }
            Object dataNode = list.data;
            list.data = data;
            return (T) dataNode;
        }
    }

    /**
     * 查询单一数据
     * @param index 要查询数据的下标
     * @param flag 通过正序还是逆序
     * @return 返回结果
     */
    private Node put(Node list, int index, boolean flag){
        if(flag){//正序查找
            while(index>0){
                list = list.next;
                index--;
            }
        } else {
            while (index<this.size-1){
                list = list.last;
                index++;
            }
        }
        return list;
    }
    /**
     * 对数据进行数组化处理
     * @param list 链表
     * @param flag 是否正序
     * @return 返回结构
     */
    private T[] array(Node list, boolean flag){
        Object array[] = new Object[this.size];
        int length = 0;
        while(list!=null){
            array[length++] = list.data;
            list=  flag?list.next : list.last;
        }
        return (T[]) array;
    }
    private class Node<T> {
        private T data;//保存数据
        private Node next;//存储下一个结点的地址
        private Node last;//保存上一个数据

        private Node(T data) {
            this.data = data;
        }
    }
}
public class DoublyLinkDemo {
    public static void main(String[] args) {
        DoublyLinkImpl<String> link = new DoublyLinkImpl<>();
        link.add("A");
        link.add("B");
        link.add("C");
        System.out.println(link.get(1));
        System.out.println("删除数据前"+link.size());
        System.out.println(link.remove(1));
        System.out.println("删除数据后"+link.size());
        System.out.println(Arrays.toString(link.toArrayJust()));
        System.out.println(Arrays.toString(link.toArrayAgainst()));
    }
}
